COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%normal.tex[s86,jmc]		Normality logic
C00016 00003	\noindent The first version of normal.tex[s86,jmc] is dated 1986 April 26.
C00017 ENDMK
C⊗;
%normal.tex[s86,jmc]		Normality logic
\input memo.tex[let,jmc]
\def\N{\mathop{N}}
\centerline{draft draft draft}
\vskip .5in
\centerline{\bf NORMALITY LOGIC}
\vskip .1in
\centerline{John McCarthy, Stanford University}
\vskip .3in
\noindent {\bf The logic.}

	Normality logic is a non-monotonic modal logic.  AI applications
will probably require a version where the modal operator
is replaced by a function on wffs, but for studying
the normality modal operator in isolation, a modal logic is convenient.

	$\N p$ is read ``normally $p$''.  Don't confuse our appropriation
of $\N$ for ``normally'' with the use of $N$ for ``necessarily''; there
are plenty of other notations for ``necessarily''.

	The wffs of {\it normality logic} are formed in the usual
way from atomic formulas, propositional connectives, quantifiers
and the modal operator $N$.  Our initial considerations will involve
the propositional logic, but we believe that as long as quantifiers
don't occur under the operator $N$, our results will also apply.
For example, formulas of the propositional version include
$p$, $p∧q$, $N p$, $N p ∧ ¬p$ and $¬\N(\N p ∧ ¬p)$.  A simple formula
of the predicate normality logic is $(∀x.bird x ⊃ N(flies x)$.

	A particular {\it normality language} is defined by choosing a
particular collection of predicate letters with arities, this includes
propositional letters considered as predicate letters with arity 0.
A {\it propositional} normality language has only propositional letters.

	An interpretation $I$ of a language $L$ is an assignment of
truth values to the wffs of $L$ such that

	1. The truth tables for the propositional connectives and
the quantifiers are satisfied.  Thus if $\pi$ and $\rho$ are assigned
$T$, then $\pi ∧ \rho$ must also be assigned $T$.

	2. $N \pi$ is assigned $T$ for all tautologous $\pi$ (including
tautologies of predicate logic in the version with predicates).

	3. Whenever $N \pi$ and $N(\pi ⊃ \rho)$ are assigned $T$,
$\rho$ is also assigned $T$.  Thus normality is preserved under
modus ponens.

	4? I haven't decided whether, when $N \pi$ and $\N \rho$ are
assigned $T$, $\N(\pi ∧ \rho)$ should also be assigned $T$.  For
now we won't do it.

	A model of a wff $\pi$ is an interpretation in which
$\pi$ is assigned $T$.  We similarly define a model of a set $A$
of wffs.  Since a model of a finite set is just a model of its
conjunction, models of sets give something new only
when $A$ may be infinite.  For simplicity we will generally refer
to models of wffs, but will use the result extended to models of
sets of wffs when this is correct and not confusing.

	The above is routine for modal logic.  Now comes
the non-monotonic part.

	Let $I$ be an interpretation.  An {\it anomaly} is a wff
$\pi$ such that $I$ assigns $T$ to $N \pi$ and $F$ to $\pi$, i.e.
something that is normally true is false.  Let $anomalies(I)$ denote
the set of anomalies of the interpretation $I$.  We are interested
in models with minimal sets of anomalies in a certain orderings.
The normality logic we obtain depends on the ordering.

	The most straightforward ordering is given by set inclusion.
Thus a {\it minimal model} of formula $\pi$ is a model $I$ such
that there is no model $I'$ of $\pi$ such that $anomalies(I')$ is
a proper subset of $anomalies(I)$.  We will say that $\pi$ is
{\it minimally entailed} by $A$ if $\pi$ is true in all minimal models
of $A$.  Unfortunately, it appears that AI will require a more
complex ordering that we will discuss after a motivating example.

	Note that the minimal models of a tautology have no anomalies at
all.  Indeed the minimal models of any satisfiable set of wffs none of
which contain $N$ have no anomalies.  On the other hand the minimal models
of $N p ∧ ¬p$ for some propositional letter $p$ must have at least the
anomaly $p$ --- once we have proved models to exist.  Therefore, minimal
entailment is obviously non-monotonic.

\noindent {\bf The Birds}.

	Before discussing the logic further, we give an example of its
intended application.  The axioms about birds' flying in [McCarthy 1986]
may be expressed as follows in normality logic.
%
$$∀x.\N\N ¬flies x,\leqno(1)$$
%
$$∀x.bird x ⊃ \N\N¬\N ¬flies x,\leqno(2)$$
%
$$∀x.bird x ⊃ \N\N flies x,\leqno(3)$$
%
$$∀x.ostrich x ⊃ \N\N¬\N¬\N ¬flies x ∧ \N\N ¬\N flies x,\leqno(4)$$
%
and
%
$$∀x.ostrich x ⊃ \N\N ¬flies x.\leqno(5)$$

	This calls for some explanation.  (1) says that objects
normally don't fly, but notice that $\N$ is iterated.  That's so
(2) can assert that being a bird normally cancels the effect
of (1).  (3) asserts that birds normally can
fly --- again in a cancellable form.  (4) cancels
the effects of (2) and (3).  (5) asserts
that ostriches normally can't fly, but again in a form that might be
cancelled by additional axioms.

	The idea behind this form of axiomatization is to keep everything
cancellable.  $\N\N p$ by itself has the same effect as $\N p$, since it
can be true and $p$ false with a single anomaly.  We can
cancel its effect by $q ⊃ ¬\N p$, but this isn't good enough if we
want the cancellation to be cancellable.  For this we must say
$q ⊃ \N\N¬\N p$.

	Unfortunately, the above axioms with the above notion of
minimality admit undesired minimal models.  Namely, it is possible
to avoid an abnormality in (1) by admitting unwanted abnormalities
in (2) and (3), so a bird needn't be able to fly after all.  Removing
the $\N\N$ from (2) and (3) would fix this problem, but then
the ability of birds to fly wouldn't itself be cancellable.

	The solution seems to be to change our ordering on interpretations
and the resulting concept of minimal model.  The idea is that
if the wff $\pi$ has $\rho$ as a subformula, we prefer making
$\rho$ anomalous to making $\pi$ anomalous.  In the above example
$\pi$ is $\N ¬N ¬flies x$ and $\rho$ is $\N ¬flies x$, or rather these
formulas with $x$ instantiated.  Extending the ordering in this way
reduces the set of minimal models.

\noindent {\bf Conjectures.}

	At present we haven't yet proved much about normality logic.
Consider first the propositional case.

	When we are minimizing anomalies, we want to give $\N\pi$ the
same truth value as $\pi$ as much as possible.
In so far as we do this, $\N$ is an identity operator, and the logic
behaves like ordinary propositional logic.  The only obstacles to always
giving $\N\pi$ the same truth value as $\pi$ come from the formula
we are trying to model.  Therefore, we conjecture that a minimal model
of $\pi$ will have as its only anomalies subformulas of $\pi$ and
formulas tautologically equivalent to them.  Essentially there will
be only a finite set of anomalies.  Moreover, there will be a finite
set of minimal models determinable by a finite process.

	Normality logic can presumably be formulated using circumscription.
All we need do is reify the logic so that the wffs become objects, express
the axioms in this form, introduce a predicate $anomalous$ and circumscribe
it.  However, it isn't obvious and presently seems unlikely that
circumscription will provide an easy way of finding minimal models.

\noindent {\bf Motivation.}

	The reason for introducing normality logic is to try to overcome
some of the disadvantages of present axiomatizations using circumscription.
However, as a mathematical logic, it seems likely to acquire a life of its
own, since it has interesting properties.

	Some of the considerations are the following.

	1. The explicit appearance of abnormalities either as predicates
or as aspects in circumscriptive formulations has seemed suspicious,
because there doesn't seem to be anything like it in human psychology.
This isn't a decisive objection for AI, of course.

	2. This led to the idea that perhaps a non-monotonic modal
operator $normally$ could be devised that would ``compile'' into
a circumscriptive formalism.  The present normality logic doesn't
seem to call for compilation into circumscription, but we are keeping
the idea in reserve.

	3. A key hope is that formulas of normality logic will be
modular and learnable from experience.  Circumscription is not
as modular as one would like, because the learning mechanism at
least has to keep track of the aspects already in use.

	Alas, this form of the logic is clobbered by a message from
Joe Halpern s86.in[let,jmc]/213p which establishes that if a set of
sentences doesn't admit a model without anomalies, then all models
are minimal, because any two models are incomparable.

	There are two possible ways out.  Change the ordering, perhaps
so that in the ordering one doesn't care about disjunctions being
anomalous, or apply $N$ only to atomic formulas.  The first looks
better.
\noindent The first version of normal.tex[s86,jmc] is dated 1986 April 26.
\noindent This version \TeX ed on \jmcdate\space at \theTime.
\eject
\end